Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт до лабораторної роботи № 1 На тему: Бітова арифметика. Алгоритмічна реалізація коду Грея. Створення консольних Windows-програм на основі Microsoft Visual Studio .NET Варіант №15  Мета роботи: отримати навики по розробленню консольних Windows-програм CLR за допомогою інструментарію Visual C++ 2005, алгоритмічно реалізувати кодер/декодер Грея, дослідити основні бітові операції алгоритмічної мови С++ та на їх основі навчитися виконувати різноманітні маніпуляції над бітовими послідовностями. Завдання Для заданого числа А вибрати необхідний цілочисельний тип даних C++, що відповідає кількості розрядам n. Написати консольну CLR програму, яка реалізує такий алгоритм (після кожного пункту вивести отриманий результат в десятковій та двійковій формах; наступні обчислення проводяться для модифікованого значення попереднього пункту): Вивести число А у консолі. Порахувати кількість розрядів, що займає число А. Перетворити число А у код Грея. Підрахувати к-сть одиничних бітів тривіальним способом. Визначити парність біт. послідовності за формулою (5.2). Здійснити інверсію 0, 2, 3 бітів Виконати реверс бітів у кожному байті біт. послідовності методом перемішування. n = 8 A=168 Теоретичні відомості Реверс бітів. Під операцією реверса бітів мається на увазі відображення вмісту слова відносно його середини, тобто розміщення бітів у слові у зворотному порядку: rev(0x01234567)=0xE6A2C480 rev(00000001001000110100010101100111) = 11100110101000101100010010000000 h 1. Тривіальний спосіб. У циклі побітово зчитується усе слово та записується у нове слово. Зчитування починається з наймолодшого біту до найстаршого заданого слова. Зчитаний біт записується у наймолодший біт нового слова, яке після цього зсувається на 1 біт вліво. unsigned int word = 3093512288, revers, mask; mask = 1; revers = 0; for (int i=0;i<32;i++) { revers = revers << 1; if (word & mask) revers = revers ^ 1; mask = mask << 1; } //word: 10111000011000110100000001100000 //revers 00000110000000101100011000011101 h 2. Метод перемішування. Спершу міняються місцями сусідні біти, потім – сусідні 2-бітові поля, далі – сусідні 4-бітові поля і т.д. Перемішування можна виконувати і у зворотному порядку. Алгоритмічно це реалізовується шляхом накладання відповідних числових масок операцією AND та зсувом на сусідню позицію, аналогічно з сусідньої позиції профільтровані значення суміжною маскою зсуваються в протилежний бік. Для слова з
виглядає так: unsigned int word = 3093512288; word = (word & 0x55555555) << 1 | (word & 0xAAAAAAAA) >> 1; word = (word & 0x33333333) << 2 | (word & 0xCCCCCCCC) >> 2; word = (word & 0x0F0F0F0F) << 4 | (word & 0xF0F0F0F0) >> 4; word = (word & 0x00FF00FF) << 8 | (word & 0xFF00FF00) >> 8; word = (word & 0x0000FFFF) << 16 | (word & 0xFFFF0000) >> 16; Код Грея Код Грея отримав свою назву по імені фізика Франка Грея (Frank Gray). Цей код, який ще називають рефлексним (відбитим), застосовують у пристроях, що перетворюють вимірювану величину в двійковий код. Якщо при такому перетворенні використовується звичайний двійковий код, то деякі розташовані поряд кодові комбінації відрізняються в декількох розрядах. Наприклад, комбінація 0111 (цифра 7) та 1000 (цифра 8) відрізняються у всіх розрядах, і тому при зчитуванні може виникнути велика похибка. Натомість, код Грея при переході від однієї кодової комбінації до сусідньої відрізняється лише одним розрядом (табл. 6.1). Кодування. Звичайний двійковий код перетворюється в код Грея шляхом сумування по модулю 2 даної комбінації з такою ж, але зсунутою вправо на один розряд.
(6.1) Мовою С++ це виглядає так: unsigned int Bin = 123456789, Gray; Gray = Bin ^ (Bin >> 1); Декодування. Перетворення коду Грея в двійковий починається з молодшого розряду шляхом сумування за модулем 2 цифр у коді Грея, починаючи зі старш...